package cn.jietuo.first.class05;


import java.util.*;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/9
 * @description: 前缀树 假定每次添加的字符串都是小写字母
 */
public class Code01_Tire {

    /**
     * 固定数组实现前缀树
     */
    public static class TireNode1 {
        public int pass;
        public int end;
        public TireNode1[] nexts;

        public TireNode1() {
            super();
            pass = 0;
            end = 0;
            // a b c ... z  一个代表一条路径
            nexts = new TireNode1[26];
        }
    }

    /**
     * 前缀树
     */
    public static class Tire1 {

        private TireNode1 root;

        public Tire1() {
            // 初始化，创建根节点
            root = new TireNode1();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            // 先转化为字符数组
            char[] chars = word.toCharArray();
            TireNode1 node = root;
            node.pass++;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TireNode1();
                }
                node = node.nexts[index];
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            // 先看有没有
            if (search(word) != 0) {
                char[] chars = word.toCharArray();
                TireNode1 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    if (--node.nexts[index].pass == 0) {
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }

        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TireNode1 node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        public int prefixNumber(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TireNode1 node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

    /**
     * 哈希表实现前缀树
     */
    public static class TireNode2 {
        public int pass;
        public int end;
        public Map<Integer, TireNode2> nexts;

        public TireNode2() {
            nexts = new HashMap<Integer, TireNode2>();
            pass = 0;
            end = 0;
        }
    }

    /**
     * 前缀树
     */
    public static class Tire2 {

        private TireNode2 root;

        public Tire2() {
            // 初始化，创建根节点
            root = new TireNode2();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            // 先转化为字符数组
            char[] chars = word.toCharArray();
            TireNode2 node = root;
            node.pass++;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!node.nexts.containsKey(index)) {
                    node.nexts.put(index, new TireNode2());
                }
                node = node.nexts.get(index);
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            // 先看有没有
            if (search(word) != 0) {
                char[] chars = word.toCharArray();
                TireNode2 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chars.length; i++) {
                    index = chars[i];
                    if (--node.nexts.get(index).pass == 0) {
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }
        }

        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TireNode2 node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end;
        }

        public int prefixNumber(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TireNode2 node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass;
        }


    }

    /**
     * for test
     */
    public static class Right {

        private Map<String, Integer> contains;

        public Right() {
            contains = new HashMap<String, Integer>();
        }

        public void insert(String word) {
            if (contains.containsKey(word)) {
                contains.put(word, contains.get(word) + 1);
            } else {
                contains.put(word, 1);
            }
        }

        public void delete(String word) {
            if (contains.containsKey(word)) {
                if (contains.get(word) == 1) {
                    contains.remove(word);
                } else {
                    contains.put(word, contains.get(word) - 1);
                }
            }
        }

        public int search(String word) {
            if (contains.containsKey(word)) {
                return contains.get(word);
            } else {
                return 0;
            }
        }


        public int prefixNumber(String word) {
            if (word == null) {
                return 0;
            }
            int count = 0;
            for (String str : contains.keySet()) {
                if (str.startsWith(word)) {
                    count += contains.get(str);
                }
            }
            return count;
        }
    }

    /**
     * 使用对数器验证程序的正确性
     *
     * @param args
     */
    public static void main(String[] args) {
        int arrlen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String arr[] = generateRandomStringArray(arrlen, strLen);
            Tire1 tire1 = new Tire1();
            Tire2 tire2 = new Tire2();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    tire1.insert(arr[j]);
                    tire2.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    tire1.delete(arr[j]);
                    tire2.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = tire1.search(arr[j]);
                    int ans2 = tire2.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("~~~Oops!!!");
                    }
                } else {
                    int ans1 = tire1.prefixNumber(arr[j]);
                    int ans2 = tire2.prefixNumber(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("----Oops!!!");
                    }
                }
            }
        }
        System.out.println("Nice");
    }

    private static String[] generateRandomStringArray(int arrlen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrlen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    private static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

}
